/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓CS206␈↓ ¬TFINAL EXAMINATION␈↓ 
lFALL 1981 

␈↓ α∧␈↓␈↓ αTThis␈α
examination␈α
is␈α
open␈α∞book␈α
and␈α
notes.␈α
 Write␈α∞LISP␈α
functions␈α
or␈α
predicates␈α∞and␈α
make
␈↓ α∧␈↓proofs␈αas␈αfollows␈α
except␈αwhere␈αsomething␈α
else␈αis␈αrequested.␈α
 Either␈αnotation␈αmay␈α
be␈αused.␈α Be␈α
sure
␈↓ α∧␈↓to␈α
indicate␈α
in␈α
an␈α
emphatic␈α
way␈α
the␈α
logical␈αsentences␈α
indicating␈α
what␈α
is␈α
to␈α
be␈α
proved␈α
and␈α
the␈α␈↓	F␈↓'s␈α
of
␈↓ α∧␈↓any␈αinductions␈α
that␈αneed␈α
to␈αbe␈αmade.␈α
 You␈αmay␈α
assume␈αthat␈αyour␈α
functions␈αare␈α
total␈αbut␈α
will␈αbe
␈↓ α∧␈↓suitably penalized if they aren't.

␈↓ α∧␈↓␈↓ αTThe␈α
examination␈α
is␈αa␈α
"take␈α
home"␈α
and␈αis␈α
due␈α
at␈α
1981␈αDecember␈α
17␈α
Thursday␈α
7pm␈αin␈α
Room
␈↓ α∧␈↓353␈α∞Margaret␈α∞Jacks␈α∞Hall.␈α∞ It␈α∂may␈α∞also␈α∞be␈α∞left␈α∞earlier␈α∂with␈α∞Mrs.␈α∞Larson␈α∞in␈α∞Room␈α∂358␈α∞Margaret
␈↓ α∧␈↓Jacks Hall.

␈↓ α∧␈↓1. Derived functions

␈↓ α∧␈↓␈↓ αTCertain␈α⊃properties␈α∩of␈α⊃LISP␈α∩functions␈α⊃are␈α∩expressed␈α⊃by␈α∩related␈α⊃functions␈α∩called␈α⊃derived
␈↓ α∧␈↓functions.  For example, consider

␈↓ α∧␈↓␈↓↓flatten x ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t x ␈↓αthen␈↓↓ <x> ␈↓αelse␈↓↓ flatten ␈↓αa␈↓↓ x * flatten ␈↓αd␈↓↓ x␈↓.

␈↓ α∧␈↓Let␈α␈↓↓cflatten␈αx␈↓␈αbe␈αthe␈αnumber␈αof␈αtimes␈αLISP␈αexecutes␈α␈↓↓cons␈↓␈αin␈αevaluating␈α␈↓↓flatten␈αx␈↓.␈α Clearly␈α
␈↓↓cflatten␈↓
␈↓ α∧␈↓satisfies the recursions

␈↓ α∧␈↓␈↓↓cflatten x ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t x ␈↓αthen␈↓↓ 1

␈↓ α∧␈↓↓␈↓ αT␈↓αelse␈↓↓ cflatten ␈↓αa␈↓↓ x + cflatten ␈↓αd␈↓↓ x + cappend[flatten ␈↓αa␈↓↓ x, flatten ␈↓αd␈↓↓ x]␈↓,

␈↓ α∧␈↓↓where cappend[u,v] is the number of conses done in computing u*v␈↓ and satisfies

␈↓ α∧␈↓␈↓↓cappend[u,v] ← ␈↓αif␈↓↓ ␈↓αn␈↓↓ u then 0 ␈↓αelse␈↓↓ 1 + cappend[␈↓αd␈↓↓ u, v]␈↓.

␈↓ α∧␈↓␈↓ αTOur other way of flattening a list involves

␈↓ α∧␈↓␈↓↓flat[x,u] ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t x ␈↓αthen␈↓↓ x.u ␈↓αelse␈↓↓ flat[␈↓αa␈↓↓ x, flat[␈↓αd␈↓↓ x, u]]␈↓.

␈↓ α∧␈↓Let ␈↓↓cflat[x,u]␈↓ be the number of ␈↓↓cons␈↓es done in computing ␈↓↓flat[x,u]␈↓.

␈↓ α∧␈↓␈↓ αTa. Write the recursion for ␈↓↓cflat[x,u]␈↓.

␈↓ α∧␈↓␈↓ αTb. Prove ␈↓↓cflat[x,u] ≤ cflatten x␈↓.

␈↓ α∧␈↓2. Occurrences of an atom in an S-expression.

␈↓ α∧␈↓␈↓ αTDefine

␈↓ α∧␈↓␈↓↓occurs[x,y] ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t y ␈↓αthen␈↓↓ x = y ␈↓αelse␈↓↓ occurs[x, ␈↓αa␈↓↓ y] ∨ occurs[x, ␈↓αd␈↓↓ y]␈↓.

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓↓occurrences[x,y,u]␈α⊗←␈α⊗␈↓αif␈↓↓␈α⊗␈↓αa␈↓↓t␈α⊗y␈α⊗␈↓αthen␈↓↓␈α⊗[␈↓αif␈↓↓␈α⊗x␈α⊗=␈α⊗y␈α⊗␈↓αthen␈↓↓␈α⊗x.u␈α⊗␈↓αelse␈↓↓␈α⊗u]␈α⊗␈↓αelse␈↓↓␈α⊗occurrences[x,␈α⊗␈↓αa␈↓↓␈α⊗y,
␈↓ α∧␈↓↓occurrences[x,␈↓αd␈↓↓ y, u]]␈↓.
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓Prove

␈↓ α∧␈↓␈↓ αT␈↓↓∀x.atom x ⊃ ∀y.occurs[x,y] ≡ member[x, occurrences[x,y,␈↓NIL␈↓↓]]␈↓.

␈↓ α∧␈↓3. Improving LCOM4

␈↓ α∧␈↓␈↓ αTPage␈α172␈αof␈αthe␈αtext␈αgives␈αcode␈αcompiled␈αby␈αLCOM4␈αfor␈αthe␈αfunction␈α␈↓↓drop␈↓␈αdefined␈αslightly
␈↓ α∧␈↓earlier in the text.

␈↓ α∧␈↓a. Why is the second executed instruction (MOVE 1 0 P) unnecessary?

␈↓ α∧␈↓b.␈α∂Describe␈α∂modifications␈α∂to␈α∂LCOM4␈α∞that␈α∂would␈α∂(preserving␈α∂correctness)␈α∂avoid␈α∂generating␈α∞this
␈↓ α∧␈↓instruction.

␈↓ α∧␈↓4 Pattern matching and substitution

␈↓ α∧␈↓␈↓ αT␈↓↓sublis[pattern,␈αalist]␈↓␈αis␈αthe␈αresult␈αof␈αmaking␈αthe␈αsubstitutions␈αdescribed␈αin␈α␈↓↓alist␈↓␈αin␈α␈↓↓pattern.␈↓
␈↓ α∧␈↓Thus

␈↓ α∧␈↓␈↓↓sublis␈↓[(PLUS␈α
X␈α
(TIMES␈α
X␈α
Y)␈α
A),␈α
((X.A)␈α
(Y.(PLUS␈α
X␈α
Y)))]␈α
=␈α
(PLUS␈α
A␈α
(TIMES␈α
A␈α∞(PLUS␈α
X
␈↓ α∧␈↓Y)) A)

␈↓ α∧␈↓␈↓↓match[pattern,expression,alist]␈↓␈α∪attempts␈α∪to␈α∪match␈α∪␈↓↓pattern␈↓␈α∪against␈α∪␈↓↓expression␈↓␈α∪to␈α∪produce␈α∪and
␈↓ α∧␈↓extension␈αof␈α␈↓↓alist␈↓␈αsuch␈αthat␈αsubstituting␈αin␈αthe␈αpattern␈αaccording␈αto␈αthe␈αresult␈αwill␈αlead␈αgive␈αback
␈↓ α∧␈↓␈↓↓expression␈↓.␈α If␈α
the␈αmatch␈α
is␈αunsuccessful,␈αthe␈α
value␈αis␈α
the␈αatom␈αNO.␈α
 It␈αis␈α
assumed␈αthat␈αa␈α
predicate
␈↓ α∧␈↓␈↓↓isvar␈↓␈α∞applicable␈α∞to␈α∂atoms␈α∞is␈α∞available␈α∞that␈α∂distinguishes␈α∞variables␈α∞from␈α∞other␈α∂atoms.␈α∞ Assuming
␈↓ α∧␈↓that ␈↓↓X␈↓ and ␈↓↓Y␈↓ are variables, we have

␈↓ α∧␈↓␈↓↓match␈↓[(PLUS X Y), (PLUS A (TIMES B C)),NIL] = ((X.A) (Y TIMES B C)),

␈↓ α∧␈↓and

␈↓ α∧␈↓␈↓↓match␈↓[(PLUS X Y), (PLUS A (TIMES B C)),((X.B))] = NO.

␈↓ α∧␈↓a. Write recursive programs for ␈↓↓sublis␈↓ and ␈↓↓match.␈↓

␈↓ α∧␈↓b. Write accurately the sentence that expresses the fact that ␈↓↓sublis␈↓ and ␈↓↓match␈↓ are partial inverses.

␈↓ α∧␈↓c. Prove the sentence of part b.

␈↓ α∧␈↓5. Simplifying expressions

␈↓ α∧␈↓␈↓ αTWrite␈α
a␈α
program␈α
for␈α
simplifying␈α
expressions␈α
formed␈α
from␈α
sums␈α
and␈α
products␈α
of␈α
arbitrary
␈↓ α∧␈↓length that

␈↓ α∧␈↓(1) appropriately eliminates sums and products with zero or one terms.

␈↓ α∧␈↓(2) drops summands that are 0 and factors that are 1

␈↓ α∧␈↓(3) drops products that have a term that is 0
␈↓ α∧␈↓␈↓ u3


␈↓ α∧␈↓b.␈αProve␈αthat␈αfor␈αall␈αvalues␈αof␈αthe␈αvariables,␈αthe␈αsimplified␈αexpression␈αhas␈αthe␈αsame␈αvalue␈αas␈αthe
␈↓ α∧␈↓original expression.

␈↓ α∧␈↓c.␈α∩Define␈α⊃an␈α∩appropriate␈α⊃complexity␈α∩and␈α⊃prove␈α∩that␈α⊃the␈α∩result␈α⊃of␈α∩simplification␈α⊃is␈α∩not␈α⊃more
␈↓ α∧␈↓complex than the input.